// https://www.lintcode.com/problem/space-replacement/description?_from=ladder&&fromId=6
// Write a method to replace all spaces in a string with %20. The string is given in a characters array, you can assume 
// it has enough space for replacement and you are given the true length of the string.

// You code should also return the new length of the string after replacement.
// You need to change the string in-place and return the new length.

class Solution {
public:
    /*
     * @param string: An array of Char
     * @param length: The true length of the string
     * @return: The true length of new string
     */
    int replaceBlank(char string[], int length) {
        int pos = 0;
        int new_len = 0;
        while (pos < length)
        {
            if (string[pos++] == ' ') new_len++;
        }
        new_len = new_len * 2 + length;
        pos--;
        for (int i = new_len - 1; i >= 0;)
        {
            if (string[pos] != ' ')
            {
                string[i--] = string[pos--];
            }
            else
            {
                string[i - 2] = '%';
                string[i - 1] = '2';
                string[i] = '0';
                pos--;
                i -= 3;
            }
        }
        return new_len;
    }
};